Networks are a principal means of exchanging or transferring information, such as signals representing voice, audio, text or video, among communication devices. Such communication devices often include devices for sending and/or receiving information, such as computer terminals, multimedia workstations, facsimile machines, printers, servers and telephones. The exchange or transfer of information is referred to as a call or connection. Information transmitted on the network can be of many different forms but is often formatted into fixed-length packets or cells.
A network typically includes switching nodes having ports coupled by links to ports of other nodes and to the communication devices. Each link is uni- or bi-directional and is characterized by a bandwidth or link capacity in the directions of data transfer. Information to be exchanged is often conveyed over a path containing a set of nodes and links connecting two communication devices. The path can be regarded as a "virtual circuit" (VC) whereby one communication device specifies the intended destination for the information, and the network delivers the information as though a dedicated circuit connected the two communication devices.
Networks, such as broadband ISDN (BISDN) employing asynchronous transfer mode (ATM) packet switching, are increasingly being used for the reliable, high-speed transmission of information. This increased use has brought major changes in network architecture and infrastructure design as well as in network operations and/or in the classes of services offered over the network. Classes of services offered over a network can include, for example, video-on-demand and video teleconferencing. Moreover, particular classes of services, such as video teleconferencing, are relatively sensitive to routing delays and receive higher routing priorities than other service classes, such as video-on-demand, which are relatively delay insensitive.
In order to extract high revenues from a network, it is advantageous for network managers to operate the network at a relatively high call capacity, i.e., establishing and maintaining a large number of simultaneous VC's. Improvement in efficiency of allocating network resources, such as transmission capacity of the links and buffer memory space, among different classes of services is one method for enabling such high capacity. Buffer memories are typically employed in the nodes to increase the number of VC's carried by the node by buffering transmission of data cells that are relatively delay insensitive while buffering to a lesser extent transmission of those data cells that are relatively delay sensitive. Such buffer memories effectively operate as respective queues for the data packets that are to be conveyed through the respective ports.
Some data services provided by a network manager are based on a grade of service commitment. For example, a network manager and a network user may agree that each VC established for that user is to have a particular committed information rate (CIR), and/or maximum information loss probability. Thus, a quiescent user seeking to start up sending data over a VC expects to receive a grade of service almost immediately that corresponds to its CIR. An admission controller is often used to restrict the total number of VC's at each node, and to monitor the sums of the CIR's for the VC's that have been established. Admission controllers are generally described in A. Elwalid and D. Mitra, "Effective Bandwidth of General Markovian Traffic Sources and Admission Control of High Speed Networks," IEEE INFOCOM '93, pp. 256-264 (1993), which is incorporated by reference herein. Moreover, the CIR's can be based on, for example, the priority levels of data cells that are transmitted. Priorities of a data cell transmitted over an BISDN network are often assigned prior to transmission of the cell and indicated as a cell loss priority bit of an ATM data packet.
It is common for a VC to require bandwidth in excess of its CIR. Since many data sources often provide bursts of data instead of a relatively steady stream of data, a network typically maintains bandwidth and buffer memory in excess of the sum of the CIR's of the active VC's. As a consequence, it is generally desirable that the network manager be responsive in providing extra bandwidth or buffer memory resources to a VC, even if the amount required is in excess of the VC's CIR, provided that such resource provision can be done while meeting the CIR's for other established VC's. More specifically, the particular method chosen for allocation of shared buffer memory between multiple output ports in a multi-port node is important so as not to unfairly deny conveyance of data cells for one VC relative to conveyance of data cells for another VC. If a data cell transmitted over a VC is denied conveyance, it will undesirably not reach its destination communication device and be considered a lost data packet in the network.
Exemplary buffer memory management methods include the complete sharing of network resources among data cells conveyed over established VC's. However, in accordance with this technique, it is possible for data cells of one VC to disadvantageously overwhelm all others and use substantially all available buffer memory preventing data cells of other VC's from sharing such memory. Another sharing technique is complete partitioning which partitions the buffer memory based on respective data cell classes. Complete partitioning enables data cells destined for a respective node output port exclusive use of an allocated portion of buffer memory. However, unused portions of buffer memory assigned to one port may not be used by data cells destined for another port often resulting in a reduced allocation efficiency.
Dynamic thresholding (DT) is a shared memory allocation technique providing enhanced performance over the complete sharing and complete partitioning methods. The DT technique employs respective queues of data packets for each of the output ports of a multi-port switch. The permissible length for any of the individual queues at any instant in time is a function of unused shared buffer memory in the switch at that time. If admission by the switch of a received data packet that is destined for a particular output port would cause the queue for that port to exceed its permissible length, then admission of the data cell would be denied.
Since the permissible lengths of the queues are dynamically changed as data packets are conveyed through the output ports or added to the queues, the technique dynamically adapts to uncertain and changing load conditions. This technique improves fairness and efficiency by guaranteeing access to the buffer memory for all output queues and by preventing any single output queue from monopolizing the memory at the expense of the other queues. However, the technique does not allow the queue for a first output port for which established VC's are providing high traffic demand to exceed its determined length despite that the VC's of a second output port are providing low traffic demand leaving the corresponding queue partly unused.
Accordingly, a continuing need exists for buffer memory allocation methods providing even more enhanced efficiency in multi-port network nodes.